26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description

Definition

$$\begin{align} L = \text{List of integers sorted in ascending order}\\ N = |L| = \text{ Size of the list L}\\ i = \text{Index of the last unique element from partial solution}\\ j = \text{Index of the prospective element to be the last unique element from partial solution} \end{align}$$

Intuition

The idea is to find the next element $L[j]$ which is different from current element $L[i]$. Since the list $L$ is already sorted, it is guaranteed that $L[j] >= L[i]$. Thus, when $L[i] != L[j]$, we should apply these operations:

$$\begin{align} L[i + 1] = L[j]\\ i = i + 1\\ j = j + 1 \end{align}$$

These steps repeats until $j < N$, e.g., when $j$ is still a valid index.

Ilustration

Initial state

$i$ and $j$ starts pointing to the first and second elements respectively. It is safe to make $j$ point to the second element even for a list of a single element because the stop condition is $j < N$. For lists of size 1, this condition will break and the algorithm stops because $1 < 1 == false$.

i

1

1

1

2

2

3

3

j

1^st iteration

$j$ moves forward trying to find an element other than $i$

i

1

1

1

2

2

3

3

j

2^rd Iteration

$j$ moves forward and now points to a different element

i

1

1

1

2

2

3

3

j

Now we copy $L[j]$ to $L[i + 1]$ and increment both pointers

i

1

2

1

2

2

3

3

j

3^rd Iteration

$j$ moves forward and now points to a different element

i

1

1

1

2

2

3

3

j

Now we copy $L[j]$ to $L[i + 1]$ and increment both pointers

i

1

2

3

2

2

3

3

—

j

4^th Iteration

Since $j = 7$ and $7 < 7 == false$, the algorithm finishes and returns the resulting list size, in this case it is $i + 1 == 3$. Thus, the final response is:

1 2 3 2 2 3 3

Implementation

Click to reveal implementation

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        left_index, right_index = 0, 1
        n = len(nums)

        while right_index < n:
            left, right = nums[left_index], nums[right_index]

            if left != right:
                left_index += 1
                nums[left_index] = right
            
            right_index += 1
        
        return left_index + 1

Tests

import pytest
from .solution import Solution

@pytest.mark.parametrize('numbers,expected', [
    ([1, 1, 1, 2, 2, 3, 3], [1, 2, 3])
])
def test_solution(numbers, expected):
    new_size = Solution().removeDuplicates(numbers)
    assert numbers[:new_size] == expected

Time complexity

Since the list is being completely iterated from left to right through pointer $j$, the complexity is $O(n)$

Space complexity

Since the list is being modified in-place and no other allocations besides auxiliary variables are made, the complexity is $O(1)$